//
// Created by hay boy on 2022/7/21.
//

#ifndef ALGORITHMS_MAXHEAP_H
#define ALGORITHMS_MAXHEAP_H
#include "maxPriorityQueue.h"
#include "../queue/QueueException.h"
#include "../linearList/LinearList.h"
#include <iostream>
using namespace std;
template<class T>
class maxHeap :public maxPriorityQueue<T>{
protected:
    int heapSize;
    int arrayLength;
    T* heap;
public:
    explicit maxHeap(int initialCapacity=10);
    ~maxHeap(){
        delete []heap;
    }
    bool empty()const{
        return heapSize==0;
    }
    int size()const{
        return heapSize;
    }
    const T& top(){
        if(heapSize==0){
            throw QueueEmpty();
        }
        return heap[1];
    }
    void pop();
    void push(const T&);
    void initialize(T*,int);
    void deactivateArray(){
        heap = nullptr;
        arrayLength = heapSize = 0;
    }
    void output(ostream& out)const;
    template <class E>
    friend ostream& operator<<(ostream& out,const maxHeap<E>& x){
        x.output(out);
        return out;
    }

};

template<class T>
void maxHeap<T>::pop() {
    if(heapSize==0){
        throw QueueEmpty();
    }
    heap[1].~T();
    T lastElement = heap[heapSize--];
    int currentNode = 1;
    int child = 2;
    while(child <= heapSize){
        if(child<heapSize&&heap[child]<heap[child+1])
            child++;
        if(lastElement>=heap[child])
            break;
        heap[currentNode] = heap[child];
        currentNode = child;
        child *= 2;
    }
    heap[currentNode] = lastElement;
}

template<class T>
void maxHeap<T>::push(const T & theElement) {
    if(heapSize==arrayLength){
        changeLength1D(heap,arrayLength,2*arrayLength);
        arrayLength *= 2;
    }
    int currentNode = ++heapSize;
    while(currentNode!=1&&heap[currentNode/2]<theElement){
        heap[currentNode] = heap[currentNode/2];
        currentNode /= 2;
    }
    heap[currentNode] = theElement;
}

template<class T>
maxHeap<T>::maxHeap(int initialCapacity) {
    if(initialCapacity<1){
        ostringstream s;
        s<<"Initial capacity = "<<initialCapacity<<" Must be > 0";
        throw illegalParameterValue(s.str());
    }
    arrayLength = initialCapacity + 1;
    heap = new T[arrayLength];
    heapSize = 0;
}

template<class T>
void maxHeap<T>::initialize(T * theHeap, int theSize) {
    delete []heap;
    heap = theHeap;
    heapSize = theSize;
    for(int root = heapSize/2;root>=1;root--){
        T rootElement = heap[root];
        int child = 2*root;
        while(child<=heapSize){
            if(child<heapSize&&heap[child]<heap[child+1])
                child++;
            if(rootElement>=heap[child])
                break;
            heap[child/2] = heap[child];
            child *= 2;//root = child/2;
        }
        heap[child/2] = rootElement;
    }
}

template<class T>
void maxHeap<T>::output(ostream &out) const {
    copy(heap+1,heap+heapSize+1,ostream_iterator<T>(cout," "));
}

template<class T>
void heapSort(T a[], int n) {
    maxHeap<T> heap(1);
    heap.initialize(a,n);
    for(int i = n-1;i>=1;i--){
        T x = heap.top();
        heap.pop();
        a[i+1] = x;
    }
    heap.deactivateArray();
}
#endif //ALGORITHMS_MAXHEAP_H
